# 第3节最少转机——图的广度优先遍历

class Que:
    def __init__(self):
        self.x = 0  # 城市编号
        self.s = 0  # 转机次数


if __name__ == '__main__':
    que = [Que() for i in range(0, 101)]
    e = [[0 for i in range(0, 11)] for j in range(0, 11)]
    book = [0 for i in range(0, 51)]
    # 初始化二维矩阵
    n = 5  # 城市数量
    m = 7  # 航线条数
    start = 1  # 出发城市
    end = 5  # 目标城市
    flag = 0
    # 初始化二维数组
    for i, v in enumerate(range(0, n + 1)):
        for j, v2 in enumerate(range(0, n + 1)):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 9  # 设9是正无穷
    # 读入城市之间的航线
    road = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]]

    for i, v in enumerate(road):
        a = road[i][0]
        b = road[i][1]
        # 注意这里是无向图
        e[a][b] = 1
        e[b][a] = 1
    # 输出图
    for i, v in enumerate(e):
        if 0 < i <= n:
            for j, v2 in enumerate(v):
                if 0 < j <= n:
                    print(v2, end=' ')
            print()
    print()
    # 队列初始化
    head = 1
    tail = 1
    # 从start号城市出发，将start加入队列
    que[tail].x = start
    que[tail].s = 0
    tail += 1
    book[1] = start
    # 当队列不为空的时候循环队列
    while head < tail:
        cur = que[head].x  # 当前队列中的城市标号
        # 从1-n依次尝试
        for i, v in enumerate(range(0, n + 1)):
            # 是否已经在队列中
            if e[cur][i] != 9 and book[i] == 0:
                # 如果从出发城市cur到i有航班并且不再队列中，则将i号城市入队
                que[tail].x = i
                que[tail].s = que[head].s + 1
                tail += 1
                book[i] = 1
            # 达到目标城市，停止扩展，退出循环
            if que[tail].x == end:
                flag = 1
                break

        if flag == 1:
            break
        head += 1

    # 打印转机次数
    # 思考：如何记录最少转机的城市路径？
    for i, v in enumerate(que):
        if v.x != 0:
            print('城市%d,转机次数%d' % (v.x, v.s))
    print(que[tail - 1].s)
